package com.goudan.practice.array;

/**
 * 题目描述
 * 给出两个有序的整数数组A和B，请将数组B合并到数组A中，变成一个有序的数组。
 * 注意：可以假设A数组有足够的空间存放B数组的元素，A和B中初始的元素数目分别为m和n。
 *
 * 题目分析：
 * 最优解：从后往前处理,不需要开辟额外空间。从后往前，这样不需要进行冗余处理。
 */
import java.util.Arrays;

public class MergeArrayToA {

    public static void main(String[] args) {
        int[] A = new int[6];
        A[0] = 4;
        A[1] = 5;
        A[2] = 6;
        int[] B = {1, 2, 3};
        merge(A, 3, B, 3);
        System.out.println(Arrays.toString(A));
    }

    /**
     * @param a 数组a，有足够的空间合并数组b
     * @param m 数组a里面的元素个数
     * @param b 数组b
     * @param n 数组b里面的元素个数
     */
    public static void merge(int[] a, int m, int[] b, int n) {
        int i = m - 1;
        int j = n - 1;
        int index = m + n - 1;
        while (i >= 0 && j >= 0) {
            if(a[i] > b[j] ){
                a[index--] = a[i--];
            } else {
                a[index--] = b[j--];
            }
        }
        //如果A的数字比B多，则不会进入后续处理；如果B的数字比A多，则进入后续处理，将B剩余数字添加到数组A中。
        while (j >= 0) {
            a[index--] = b[j--];
        }
    }

}
